package com.github.tangmonkmeat;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/7/26 上午10:25
 */
public class 验证二叉搜索树 {

    public static void main(String[] args) {

        List<String> list = new ArrayList<>();

        list.add("123");

        List<String> list1 = new ArrayList<>();
        list1.add("321");

        //list1.to

        list.addAll(list1);

        System.out.println("");

    }

    long preVal = Long.MIN_VALUE;

    // 使用中序遍历，而二叉搜索数的中序遍历的结果一定是一个升序的结果
    // 所以，记录每次中序遍历的pre节点，now.val 必须大于 pre.val
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }

        if(!isValidBST(root.left)){
            return false;
        }

        if(root.val <= preVal){
            return false;
        }

        preVal = root.val;

        return isValidBST(root.right);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
